#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 042. 接雨水.py
@time: 2022/1/11 21:40
@desc: https://leetcode-cn.com/problems/trapping-rain-water/
> 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

@解题思路：
    1. dp
    2. Ot(n), Os(n)
'''


class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height: return 0
        n = len(height)
        left_max = [height[0]] + [0] * (n - 1)
        right_max = [0] * (n - 1) + [height[-1]]

        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        ans = sum(min(right_max[i], left_max[i]) - height[i] for i in range(n))
        return ans
